package demo.practice.stack;

import java.util.LinkedList;

public class P1249 {

    /*public String minRemoveToMakeValid(String s) {


        for(char c :s.toCharArray()){

        }
    }*/



    public static void main(String[] args) {
        P1249 p1249= new P1249();
        p1249.minRemoveToMakeValid("lee(t(c)o)de)");
    }
    public String minRemoveToMakeValid(String s) {

        LinkedList<Integer> quque= new LinkedList();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)=='(')
                //stack.add(i);
                quque.add(i);
            else if(s.charAt(i)==')' ){
                if(quque.size()>0&&s.charAt(quque.getLast())=='(')
                    quque.pollLast();
                else
                    quque.add(i);
            }
        }



       if(quque.size()==0)
           return s;

       StringBuilder sb= new StringBuilder();
       for(int i=0;i<s.length();i++){
           if(quque.size()>0 && quque.peekFirst()==i){
               quque.pollFirst();
           }else
               sb.append(s.charAt(i));
       }

       return sb.toString();
    }
}
